home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / ELECTRON / 0989.ZIP / ESPRESSO.ARC / CVRIN.C < prev    next >
Text File  |  1987-03-13  |  20KB  |  544 lines
  1. /*
  2.     module: cvrin.c
  3.     purpose: cube and cover input routines
  4. */
  5.  
  6. #include "espresso.h"
  7.  
  8. #define strsav(s)       strcpy(alloc(strlen(s)+1), s)
  9. #define abs(i)          ((i) > 0 ? (i) : -(i))
  10.  
  11. static bool echo_comments = TRUE, echo_unknown_commands = TRUE;
  12. static bool line_length_error;
  13. static int lineno;
  14.  
  15. void skip_line(fpin, fpout, echo)
  16. register FILE *fpin, *fpout;
  17. register bool echo;
  18. {
  19.     register int ch;
  20.     while ((ch=getc(fpin)) != EOF && ch != '\n')
  21.         if (echo)
  22.             putc(ch, fpout);
  23.     if (echo)
  24.         putc('\n', fpout);
  25.     lineno++;
  26. }
  27.  
  28. char *get_word(fp, word)
  29. register FILE *fp;
  30. register char *word;
  31. {
  32.     register int ch, i = 0;
  33.     while ((ch = getc(fp)) != EOF && ! isspace(ch))
  34.         word[i++] = ch;
  35.     word[i++] = '\0';
  36.     return word;
  37. }
  38. /*
  39.     cube_setup -- assume that the fields "num_vars", "num_binary_vars", and
  40.     part_size[num_binary_vars .. num_vars-1] are setup, and initialize the
  41.     rest of cube and cdata.
  42.  
  43.     If a part_size is < 0, then the field size is abs(part_size) and the
  44.     field read from the input is symbolic.
  45. */
  46. cube_setup()
  47. {
  48.     register int i, j, var;
  49.     register pcube p;
  50.  
  51.     cube.size = 0;
  52.     cube.first_part = (int *) alloc(cube.num_vars * sizeof(int));
  53.     cube.last_part = (int *) alloc(cube.num_vars * sizeof(int));
  54.     cube.first_word = (int *) alloc(cube.num_vars * sizeof(int));
  55.     cube.last_word = (int *) alloc(cube.num_vars * sizeof(int));
  56.     for(var = 0; var < cube.num_vars; var++) {
  57.         if (var < cube.num_binary_vars)
  58.             cube.part_size[var] = 2;
  59.         cube.first_part[var] = cube.size;
  60.         cube.first_word[var] = WHICH_WORD(cube.size);
  61.         cube.size += abs(cube.part_size[var]);
  62.         cube.last_part[var] = cube.size - 1;
  63.         cube.last_word[var] = WHICH_WORD(cube.size - 1);
  64.     }
  65.  
  66.     cube.var_mask = (pset *) alloc(cube.num_vars * sizeof(pset));
  67.     cube.sparse = (int *) alloc(cube.num_vars * sizeof(int));
  68.     cube.binary_mask = new_cube();
  69.     cube.mv_mask = new_cube();
  70.     for(var = 0; var < cube.num_vars; var++) {
  71.         p = cube.var_mask[var] = new_cube();
  72.         for(i = cube.first_part[var]; i <= cube.last_part[var]; i++)
  73.             set_insert(p, i);
  74.         if (var < cube.num_binary_vars) {
  75.             INLINEset_or(cube.binary_mask, cube.binary_mask, p);
  76.             cube.sparse[var] = 0;
  77.         } else {
  78.             INLINEset_or(cube.mv_mask, cube.mv_mask, p);
  79.             cube.sparse[var] = 1;
  80.         }
  81.     }
  82.     if (cube.num_binary_vars == 0)
  83.         cube.inword = -1;
  84.     else {
  85.         cube.inword = cube.last_word[cube.num_binary_vars - 1];
  86.         cube.inmask = cube.binary_mask[cube.inword] & DISJOINT;
  87.     }
  88.  
  89.     cube.temp = (pset *) alloc(CUBE_TEMP * sizeof(pset));
  90.     for(i = 0; i < CUBE_TEMP; i++)
  91.         cube.temp[i] = new_cube();
  92.     cube.fullset = set_fill(new_cube(), cube.size);
  93.     cube.emptyset = new_cube();
  94.  
  95.     if (cube.label == NULL) {
  96.         cube.label = (char ***) alloc(cube.num_vars * sizeof(char **));
  97.         for(i = 0; i < cube.num_vars; i++) {
  98.             cube.label[i] = (char **) 
  99.                 alloc( (abs(cube.part_size[i])+1) * sizeof(char *));
  100.             for(j = 0; j < abs(cube.part_size[i]); j++)
  101.                 cube.label[i][j] = NULL;
  102.         }
  103.     }
  104.  
  105.     cdata.part_zeros = (int *) alloc(cube.size * sizeof(int));
  106.     cdata.var_zeros = (int *) alloc(cube.num_vars * sizeof(int));
  107.     cdata.parts_active = (int *) alloc(cube.num_vars * sizeof(int));
  108.     cdata.is_unate = (int *) alloc(cube.num_vars * sizeof(int));
  109. }
  110. /*
  111.     set_phase -- given a "cube" which describes which phases of the output
  112.     are to be implemented, compute the appropriate on-set and off-set
  113. */
  114. pPLA set_phase(PLA)
  115. INOUT pPLA PLA;
  116. {
  117.     pcover F1, R1;
  118.     register pcube last, p, outmask;
  119.     register pcube temp=cube.temp[0], phase=PLA->phase, phase1=cube.temp[1];
  120.  
  121.     outmask = cube.var_mask[cube.num_vars - 1];
  122.     set_diff(phase1, outmask, phase);
  123.     set_or(phase1, set_diff(temp, cube.fullset, outmask), phase1);
  124.     F1 = new_cover((PLA->F)->count + (PLA->R)->count);
  125.     R1 = new_cover((PLA->F)->count + (PLA->R)->count);
  126.  
  127.     foreach_set(PLA->F, last, p) {
  128.         if (! setp_disjoint(set_and(temp, p, phase), outmask))
  129.             set_copy(GETSET(F1, F1->count++), temp);
  130.         if (! setp_disjoint(set_and(temp, p, phase1), outmask))
  131.             set_copy(GETSET(R1, R1->count++), temp);
  132.     }
  133.     foreach_set(PLA->R, last, p) {
  134.         if (! setp_disjoint(set_and(temp, p, phase), outmask))
  135.             set_copy(GETSET(R1, R1->count++), temp);
  136.         if (! setp_disjoint(set_and(temp, p, phase1), outmask))
  137.             set_copy(GETSET(F1, F1->count++), temp);
  138.     }
  139.     free_cover(PLA->F);
  140.     free_cover(PLA->R);
  141.     PLA->F = F1;
  142.     PLA->R = R1;
  143.     return PLA;
  144. }
  145. void read_cube(fp, PLA)
  146. IN register FILE *fp;
  147. INOUT pPLA PLA;
  148. {
  149.     register int var, i, len;
  150.     pcube cf = cube.temp[0], cr = cube.temp[1], cd = cube.temp[2];
  151.     bool savef = FALSE, saved = FALSE, saver = FALSE;
  152.     char line[1024];
  153.  
  154.     set_clear(cf, cube.size);
  155.     len = 0;
  156.  
  157.     /* Loop and read binary variables */
  158.     for(var = 0; var < cube.num_binary_vars; var++)
  159.         switch(line[len++] = getc(fp)) {
  160.             case EOF:
  161.                 goto bad_char;
  162.             case '\n':
  163.                 if (! line_length_error)
  164.                     fprintf(stderr, "espresso: product term(s) %s\n",
  165.                         "span more than one line (warning only)");
  166.                 line_length_error = TRUE;
  167.                 lineno++;
  168.             case ' ': case '|': case '\t':
  169.                 var--;
  170.                 break;
  171.             case '2': case '-':
  172.                 set_insert(cf, var*2+1);
  173.             case '0': 
  174.                 set_insert(cf, var*2);
  175.                 break;
  176.             case '1':
  177.                 set_insert(cf, var*2+1);
  178.                 break;
  179.             default:
  180.                 goto bad_char;
  181.         }
  182.  
  183.  
  184.     /* Loop for the all but one of the multiple-valued variables */     
  185.     for(var = cube.num_binary_vars; var < cube.num_vars-1; var++)
  186.  
  187.         /* Read a symbolic multiple-valued variable */
  188.         if (cube.part_size[var] < 0) {
  189.             char token[250]; int varx = var;
  190.             fscanf(fp, "%s", token);
  191.             if (equal(token, "-"))
  192.                 set_or(cf, cf, cube.var_mask[var]);
  193.             else {
  194.                 if (kiss && var == cube.num_vars - 2)
  195.                     varx = var - 1; /* use present state symbol table */
  196.                 /* Find the symbolic label in the label table */
  197.                 for(i = 0; cube.label[varx][i] != NULL; i++)
  198.                     if (equal(cube.label[varx][i], token)) {
  199.                         set_insert(cf, i + cube.first_part[var]);
  200.                         break;
  201.                     }
  202.                 if (cube.label[varx][i] == NULL)
  203.                     if (i == -cube.part_size[var]) {
  204.                         fprintf(stderr,"espresso: var %d, size too small\n",
  205.                             var, -cube.part_size[var]);
  206.                         exit(-1);
  207.                     } else {
  208.                         cube.label[varx][i] = strsav(token);
  209.                         set_insert(cf, i + cube.first_part[var]);
  210.                     }
  211.             }
  212.         
  213.         } else for(i = cube.first_part[var]; i <= cube.last_part[var]; i++)
  214.             switch (line[len++] = getc(fp)) {
  215.                 case EOF:
  216.                     goto bad_char;
  217.                 case '\n':
  218.                     if (! line_length_error)
  219.                         fprintf(stderr, "espresso: product term(s) %s\n",
  220.                             "span more than one line (warning only)");
  221.                     line_length_error = TRUE;
  222.                     lineno++;
  223.                 case ' ': case '|': case '\t':
  224.                     i--;
  225.                     break;
  226.                 case '1': 
  227.                     set_insert(cf, i);
  228.                 case '0': 
  229.                     break;
  230.                 default:
  231.                     goto bad_char;
  232.             }
  233.  
  234.     /* Loop for last multiple-valued variable */
  235.     if (kiss) {
  236.         saver = savef = TRUE;
  237.         set_xor(cr, cf, cube.var_mask[cube.num_vars - 2]);
  238.     } else
  239.         set_copy(cr, cf);
  240.     set_copy(cd, cf);
  241.     for(i = cube.first_part[var]; i <= cube.last_part[var]; i++)
  242.         switch (line[len++] = getc(fp)) {
  243.             case EOF:
  244.                 goto bad_char;
  245.             case '\n':
  246.                 if (! line_length_error)
  247.                     fprintf(stderr, "espresso: product term(s) %s\n",
  248.                         "span more than one line (warning only)");
  249.                 line_length_error = TRUE;
  250.                 lineno++;
  251.             case ' ': case '|': case '\t':
  252.                 i--;
  253.                 break;
  254.             case '4': case '1':
  255.                 if (PLA->pla_type & F_type)
  256.                     set_insert(cf, i), savef = TRUE;
  257.                 break;
  258.             case '3': case '0': 
  259.                 if (PLA->pla_type & R_type)
  260.                     set_insert(cr, i), saver = TRUE;
  261.                 break;
  262.             case '2': case '-':
  263.                 if (PLA->pla_type & D_type)
  264.                     set_insert(cd, i), saved = TRUE;
  265.             case '~':
  266.                 break;
  267.             default:
  268.                 goto bad_char;
  269.         }
  270.     if (savef)
  271.         PLA->F = sf_addset(PLA->F, cf);
  272.     if (saved)
  273.         PLA->D = sf_addset(PLA->D, cd);
  274.     if (saver)
  275.         PLA->R = sf_addset(PLA->R, cr);
  276.     return;
  277.  
  278. bad_char:
  279.     fprintf(stderr, "(warning): input line #%d ignored\n", lineno);
  280.     for(i = 0; i < len; i++)
  281.         putc(line[i], stdout);
  282.     skip_line(fp, stdout, TRUE);
  283.     return;
  284. }
  285. void parse_pla(fp, PLA)
  286. IN FILE *fp;
  287. INOUT pPLA PLA;
  288. {
  289.     register int i, var, ch;
  290.     int np;
  291.     char word[256];
  292.  
  293.     lineno = 1;
  294.     line_length_error = FALSE;
  295.  
  296. loop:
  297.     switch(ch = getc(fp)) {
  298.         case EOF:
  299.             return;
  300.         case '\n':
  301.             lineno++;
  302.         case ' ': case '\t': case '\f': case '\r':
  303.             break;
  304.         case '#':
  305.             ungetc(ch, fp);
  306.             skip_line(fp, stdout, echo_comments);
  307.             break;
  308.         case '.':
  309.             /* .i gives the cube input size (binary-functions only) */
  310.             if (equal(get_word(fp, word), "i")) {
  311.                 if (cube.fullset != NULL)
  312.                     fprintf(stderr, "espresso: extra .i ignored\n");
  313.                 else {
  314.                     fscanf(fp, "%d", &cube.num_binary_vars);
  315.                     cube.num_vars = cube.num_binary_vars + 1;
  316.                     cube.part_size = (int *) alloc(cube.num_vars*sizeof(int));
  317.                 }
  318.  
  319.             /* .o gives the cube output size (binary-functions only) */
  320.             } else if (equal(word, "o")) {
  321.                 if (cube.fullset != NULL)
  322.                     fprintf(stderr, "espresso: extra .o ignored\n");
  323.                 else {
  324.                     if (cube.part_size == NULL)
  325.                         fatal("espresso: .o cannot appear before .i");
  326.                     fscanf(fp, "%d", &(cube.part_size[cube.num_vars - 1]));
  327.                     cube_setup();
  328.                 }
  329.  
  330.             /* .mv gives the cube size for a multiple-valued function */
  331.             } else if (equal(word, "mv")) {
  332.                 if (cube.fullset != NULL)
  333.                     fprintf(stderr, "espresso: extra .mv ignored\n");
  334.                 else {
  335.                     if (cube.part_size != NULL)
  336.                         fatal("espresso: cannot mix .i and .mv");
  337.                     fscanf(fp,"%d %d",&cube.num_vars,&cube.num_binary_vars);
  338.                     cube.part_size = (int *) alloc(cube.num_vars*sizeof(int));
  339.                     for(var=cube.num_binary_vars; var < cube.num_vars; var++)
  340.                         fscanf(fp, "%d", &(cube.part_size[var]));
  341.                     cube_setup();
  342.                 }
  343.  
  344.             /* .p gives the number of product terms (redundant) */
  345.             } else if (equal(word, "p"))
  346.                 fscanf(fp, "%d", &np);
  347.             /* .name at one time gave a name to the pla */
  348.             else if (equal(word, "name"))
  349.                 get_word(fp, word);
  350.             /* .e and .end specify the end of the file */
  351.             else if (equal(word, "e") || equal(word,"end"))
  352.                 return;
  353.             /* .kiss turns on the kiss-hack option */
  354.             else if (equal(word, "kiss"))
  355.                 kiss = TRUE;
  356.  
  357.             /* .type specifies a logical type for the PLA */
  358.             else if (equal(word, "type")) {
  359.                 get_word(fp, word);
  360.                 for(i = 0; pla_types[i].key != 0; i++)
  361.                     if (equal(pla_types[i].key + 1, word)) {
  362.                         PLA->pla_type = pla_types[i].value;
  363.                         break;
  364.                     }
  365.                 if (pla_types[i].key == 0)
  366.                     fatal("espresso: unknown type in .type command");
  367.  
  368.             /* .phase allows a choice of output phases */
  369.             } else if (equal(word, "phase")) {
  370.                 int last;
  371.                 if (cube.fullset == NULL)
  372.                     fatal("espresso: cube size not declared before .phase");
  373.                 PLA->phase = set_save(cube.fullset);
  374.                 last = cube.last_part[cube.num_vars - 1];
  375.                 for(i = cube.first_part[cube.num_vars - 1]; i <= last; i++)
  376.                     if ((ch = getc(fp)) == '0')
  377.                         set_remove(PLA->phase, i);
  378.                     else if (ch != '1')
  379.                         fatal("espresso: bad character in phase description");
  380.  
  381.             /* .pair allows for bit-pairing input variables */
  382.             } else if (equal(word, "pair")) {
  383.                 if (PLA->pair != NULL)
  384.                     fprintf(stderr, "espresso: extra .pair ignored\n");
  385.                 else {
  386.                     ppair pair;
  387.                     PLA->pair = pair = (ppair) alloc(sizeof(pair_t));
  388.                     fscanf(fp, "%d", &(pair->cnt));
  389.                     pair->var1 = (int *) alloc(pair->cnt * sizeof(int));
  390.                     pair->var2 = (int *) alloc(pair->cnt * sizeof(int));
  391.                     for(i = 0; i < pair->cnt; i++)
  392.                         if (fscanf(fp, " ( %d %d )", &(pair->var1[i]),
  393.                           &(pair->var2[i])) != 2)
  394.                             fatal("espresso: syntax error in .pair");
  395.                 }
  396.                 
  397.             } else {
  398.                 if (echo_unknown_commands)
  399.                     printf("%c%s ", ch, word);
  400.                 skip_line(fp, stdout, echo_unknown_commands);
  401.             }
  402.             break;
  403.         default:
  404.             ungetc(ch, fp);
  405.             if (cube.fullset == NULL) {
  406. /*              fatal("espresso: unknown cube size, need .i/.o or .mv");*/
  407.                 putchar('#');
  408.                 skip_line(fp, stdout, TRUE);
  409.                 break;
  410.             }
  411.             if (PLA->F == NULL) {
  412.                 PLA->F = new_cover(10);
  413.                 PLA->D = new_cover(10);
  414.                 PLA->R = new_cover(10);
  415.             }
  416.             read_cube(fp, PLA);
  417.     }
  418.     goto loop;
  419. }
  420. /*
  421.     read_pla -- read a pla from a file
  422.         
  423.     Unpack an optional pla type from the command line.
  424.  
  425.     The next argument is assumed to be a filename or "-" to imply stdin.
  426.     (stdin is also assumed if no more arguments remain)
  427.  
  428.     We then read the actual cubes from the file and massage them into
  429.     the logical representations of an ON cover, OFF cover, and DC cover.
  430. */
  431.  
  432. pPLA read_pla(argc, argv, default_pla_type)
  433. INOUT int *argc;
  434. INOUT char *argv[];
  435. IN int default_pla_type;
  436. {
  437.     int i, var;
  438.     pPLA PLA;
  439.     FILE *fp;
  440.     double time;
  441.     cost_t cost;
  442.  
  443.     /* Allocate and initialize the PLA structure */
  444.     PLA = (pPLA) alloc(sizeof(PLA_t));
  445.     PLA->F = PLA->D = PLA->R = NULL;
  446.     PLA->phase = NULL;
  447.     PLA->pair = NULL;
  448.     PLA->pla_type = default_pla_type;
  449.  
  450.     /* Check if next command line argument specifies logical pla type */
  451.     if (*argc >= 2)
  452.         for(i = 0; pla_types[i].key != 0; i++)
  453.             if (equal(pla_types[i].key, argv[1])) {
  454.                 PLA->pla_type = pla_types[i].value;
  455.                 delete_arg(argc, argv, 1);
  456.                 break;
  457.             }
  458.  
  459.     /* Assume next argument is a filename; or read stdin if no more args */
  460.     if (*argc >= 2 && ! equal(argv[1], "-")) {
  461.         strcpy(PLA->filename, argv[1]);
  462.         if ((fp = fopen(argv[1], "r")) == NULL) {
  463.             fprintf(stderr, "espresso: can't open %s\n", argv[1]);
  464.             exit(-1);
  465.         }
  466.         delete_arg(argc, argv, 1);
  467.     } else {
  468.         strcpy(PLA->filename, "(stdin)");
  469.         fp = stdin;
  470.     }
  471.  
  472.     /* Read the pla */
  473.     time = ptime();
  474.     parse_pla(fp, PLA);
  475.     for(i = 0; i < cube.num_vars; i++)
  476.         cube.part_size[i] = abs(cube.part_size[i]);
  477.     if (kiss) {
  478.         cube.part_size[cube.num_vars-2] += cube.part_size[cube.num_vars-1];
  479.         cube.label[cube.num_vars-2] = cube.label[cube.num_vars-1];
  480.         cube.num_vars--;
  481.         cube_setup();
  482.     }
  483.     if (PLA->F == NULL)
  484.         fatal("espresso: no PLA found on input file");
  485.     if (trace)
  486.         totals(time, READ_TIME, PLA->F, &cost);
  487.  
  488.     /* Decide how to break PLA into ON-set, OFF-set and DC-set */
  489.     time = ptime();
  490.     if (PLA->pla_type == F_type || PLA->pla_type == FD_type) {
  491.         free_cover(PLA->R);
  492.         PLA->R = complement(cube2list(PLA->F, PLA->D));
  493.     } else if (PLA->pla_type == FR_type) {
  494.         pcover X;
  495.         free_cover(PLA->D);
  496.         /* hack, why not? */
  497.         X = d1merge(sf_join(PLA->F, PLA->R), cube.num_vars - 1);
  498.         PLA->D = complement(cube1list(X));
  499.         free_cover(X);
  500.     } else if (PLA->pla_type == R_type || PLA->pla_type == DR_type) {
  501.         free_cover(PLA->F);
  502.         PLA->F = complement(cube2list(PLA->D, PLA->R));
  503.     }
  504.     if (trace)
  505.         totals(time, COMPL_TIME, PLA->R, &cost);
  506.  
  507.     if (pos) {
  508.         pcover onset = PLA->F;
  509.         PLA->F = PLA->R;
  510.         PLA->R = onset;
  511.     } else if (PLA->phase != NULL)
  512.         set_phase(PLA);
  513.     if (PLA->pair != NULL)
  514.         set_pair(PLA);
  515.  
  516.     if (trace || summary) {
  517.         printf("# PLA is %s", PLA->filename);
  518.         if (cube.num_binary_vars == cube.num_vars - 1)
  519.             printf(" with %d inputs and %d outputs\n",
  520.                 cube.num_binary_vars, cube.part_size[cube.num_vars - 1]);
  521.         else {
  522.             printf(" with %d variables (%d binary, mv sizes",
  523.                 cube.num_vars, cube.num_binary_vars);
  524.             for(var = cube.num_binary_vars; var < cube.num_vars; var++)
  525.                 printf(" %d", cube.part_size[var]);
  526.             printf(")\n");
  527.         }
  528.         printf("# ON-set cost is  %s\n", print_cost(PLA->F));
  529.         printf("# OFF-set cost is %s\n", print_cost(PLA->R));
  530.         printf("# DC-set cost is  %s\n", print_cost(PLA->D));
  531.         if (PLA->phase != NULL)
  532.             printf("# phase is %s\n", pc1(PLA->phase));
  533.         if (PLA->pair != NULL) {
  534.             printf("# two-bit encoders with pairing");
  535.             for(i = 0; i < PLA->pair->cnt; i++)
  536.                 printf(" (%d %d)", PLA->pair->var1[i], PLA->pair->var2[i]);
  537.             printf("\n");
  538.         }
  539.         (void) fflush(stdout);
  540.     }
  541.  
  542.     return PLA;
  543. }
  544.